`
https://leetcode.cn/problems/sort-the-matrix-diagonally/
`

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var diagonalSort = function (mat) {
  const m = mat.length, n = mat[0].length

  const diagonals = new Map()

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 在同一个对角线上的元素，其横纵坐标之差是相同的
      // 横纵坐标之差可以作为一条对角线的 ID
      const id = i - j
      if (!diagonals.has(id)) {
        diagonals.set(id, [])
      }
      diagonals.get(id).push(mat[i][j])
    }
  }

  // 对每条对角线进行排序
  // 使用倒序，因为待会从数组尾部拿出来效率更高
  for (const d of diagonals.values()) {
    d.sort((a, b) => b - a)
  }

  // 排序完后把每条对角线的值放回数组
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const id = i - j
      mat[i][j] = diagonals.get(id).pop()
    }
  }

  return mat
};